package com.xdja.zuoye;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTreeAvg {

    public static void main(String[] args) {
        Object[] array = new Object[]{1, 2, 3, 4, 5, null, 6};
        TreeNode root = makeTree(array);
        System.out.println(calcTree(root));
    }

    private static List<Double> calcTree(TreeNode treeNode) {
        List<Double> result = new ArrayList<>();
        if (treeNode == null) {
            return result;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(treeNode);
        while (!nodeQueue.isEmpty()) {
            int size = nodeQueue.size();
            double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = nodeQueue.poll();
                if (node.left != null) {
                    nodeQueue.add(node.left);
                }
                if (node.right != null) {
                    nodeQueue.add(node.right);
                }
                sum += node.value;
            }
            result.add(sum / size);
        }
        return result;
    }

    private static TreeNode makeTree(Object[] tree) {
        List<TreeNode> list = new ArrayList<>();
        for (Object o : tree) {
            if (o != null) {
                TreeNode node = new TreeNode((Integer) o);
                list.add(node);
            } else {
                list.add(null);
            }
        }
        for (int i = 0; i < list.size(); i++) {
            TreeNode parent = list.get(i);
            if (parent != null) {
                if (list.size() > (2 * i + 1) && list.get(2 * i + 1) != null) {
                    parent.left = list.get(2 * i + 1);
                }
                if (list.size() > (2 * i + 1) && list.get(2 * i + 2) != null) {
                    parent.right = list.get(2 * i + 2);
                }
            }
        }
        return list.get(0);
    }

    public static class TreeNode {

        int value;

        TreeNode left;

        TreeNode right;

        public TreeNode() {
        }
        public TreeNode(int value) {
            this.value = value;
        }
    }

}
